package practice_2025_9.practice_9_18;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution {
    /**
     * 整数转罗马数字
     * @param num
     * @return
     */
    public String intToRoman(int num) {
        // 不以 4 或 9 开头 -> 减去最大值符号, 再继续转化
        // 以 4 和 9 开头 -> 使用 减法形式
        // 只有 10 的次方可以连续附加 3 次
        // 5 50 500 不能多次附加
        // 若符号附加 4 次 -> 使用减法
        // 按照题目模拟
        StringBuilder res = new StringBuilder();
        Map<Integer, Character> hash = new HashMap<>();
        hash.put(1, 'I');
        hash.put(5, 'V');
        hash.put(10, 'X');
        hash.put(50, 'L');
        hash.put(100, 'C');
        hash.put(500, 'D');
        hash.put(1000, 'M');
        // 判断数字的开头 -> 判断是否是 4 或 9
        while(num > 0) {
            String numStr = Integer.toString(num);
            char beginN = numStr.charAt(0);
            // 4 or 9 -> 直接处理
            if (beginN == '4' || beginN == '9') {
                // 1 位数+1, 2位数+10, 三位数 + 100
                int reduce = (int)Math.pow(10, numStr.length() - 1);
                int count = (beginN - '0') * reduce;
                // System.out.println("count: " + count + " " + reduce);
                res.append(hash.get(reduce));
                res.append(hash.get(count + reduce));
                
                num -= count;
            } else {
                // 减去最大值(全部减完)
                int max = 1;
                // 找到最大值
                for(int key : hash.keySet()) {
                    if (num - key >= 0 && key > max) {
                        max = key;
                    }
                }
                num -= max;
                res.append(hash.get(max));
//                System.out.println(num + " " + max);
            }
        }
        return res.toString();
    }

    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

    /**
     * 转罗马数字实现II
     * @param num
     * @return
     */
    public String intToRoman2(int num) {
        StringBuffer roman = new StringBuffer();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                roman.append(symbol);
            }
            if (num == 0) {
                break;
            }
        }
        return roman.toString();
    }

    /**
     * 简化路径
     * @param path
     * @return
     */
    public String simplifyPath(String path) {
        char[] chs = path.toCharArray();
        Stack<String> stack = new Stack<>();
        int i = 0;
        stack.add("/");
        while(i < chs.length) {
            if (chs[i] == '/') {
                while(i < chs.length && chs[i] == '/') {
                    i++;
                }
            } else {
                StringBuilder tmp = new StringBuilder();
                while(i < chs.length && chs[i] != '/') {
                    tmp.append(chs[i]);
                    i++;
                }
                String str = tmp.toString();
                // System.out.println(str + " " + (str == ".." && stack.size() > 1));
                if (str.equals(".")) {
                } else if (str.equals("..")) {
                    if (stack.size() > 1) {
                        stack.pop();
                    }
                } else {
                    stack.add(str);
                }
            }
        }
        String[] strs = new String[stack.size()];
        i = 0;
        while(!stack.isEmpty()) {
            strs[i++] = stack.pop();
        }
        // System.out.println(Arrays.toString(strs));
        StringBuilder res = new StringBuilder();
        for(int j = strs.length - 1; j >= 0; j--) {
            res.append(strs[j]);
            if (j != strs.length - 1 && j != 0) {
                res.append('/');
            }

        }
        return res.toString();
    }
}